import { Compare, defaultCompare, DOES_NOT_EXIST } from '../../util';
import { quickSort } from '../sorting/quick-sort';

/**
 * 二分搜索:
 * 1.在待选区间里选择一个中间值，如果中间值就是待搜索值就直接返回；
 * 2.如果待搜索值比中间值要小，就将目前区间的左区间（较小区间）作为待选区间，然后重复步骤1；
 * 3.如果待搜索值比中间值要大，就将目前区间的右区间（较大区间）作为待选区间，然后重复步骤1。
 * @param array 原数组
 * @param value 待搜索值
 * @param compareFn 比较函数
 * 迭代的方式实现
 */
export function binarySearch<T>(array: T[], value: T, compareFn = defaultCompare): number {
    // 二分搜索的前提条件是该数组已排序（默认升序），我们用快速排序先排一下
    const sortedArray = quickSort(array);
    // 待搜索区的最小值的索引
    let low: number = 0;
    // 待搜索区的最大值的索引
    let high: number = sortedArray.length - 1;

    // low大于high才停止搜索
    while (low <= high) {
        // 待搜索区的中间值
        const mid: number = low + Math.floor((high - low) / 2);
        const midValue: T = sortedArray[mid];
        // 待搜索值比中间值小，证明待搜索值在左区间，需要将最大值索引替换成mid-1
        if (compareFn(value, midValue) === Compare.LESS_THAN) {
            high = mid - 1;
        }
        // 待搜索值比中间值大，证明待搜索值在右区间，需要将最小值索引替换成mid+1
        else if (compareFn(value, midValue) === Compare.BIGGER_THAN) {
            low = mid + 1;
        }
        // 待搜索值和中间值相等，找到了，直接返回
        else {
            return mid;
        }
    }
    return DOES_NOT_EXIST;
}

/**
 * 二分搜索:
 * 1.在待选区间里选择一个中间值，如果中间值就是待搜索值就直接返回；
 * 2.如果待搜索值比中间值要小，就将目前区间的左区间（较小区间）作为待选区间，然后重复步骤1；
 * 3.如果待搜索值比中间值要大，就将目前区间的右区间（较大区间）作为待选区间，然后重复步骤1。
 * @param array 原数组
 * @param value 待搜索值
 * @param compareFn 比较函数
 * 递归的方式实现
 */
export function binarySearchRecursive<T>(array: T[], value: T, compareFn = defaultCompare): number {
    // 二分搜索的前提条件是该数组已排序（默认升序），我们用快速排序先排一下
    const sortedArray = quickSort(array);

    // 待搜索区的最小值的索引
    const low: number = 0;
    // 待搜索区的最大值的索引
    const high: number = sortedArray.length - 1;

    return binarySearchVisit(sortedArray, low, high, value, compareFn);

}

/**
 * 二分搜索的递归
 * @param array 原数组
 * @param low 待搜索区的最小值的索引
 * @param high 待搜索区的最大值的索引
 * @param value 待搜索值
 * @param compareFn 比较函数
 */
function binarySearchVisit<T>(
    array: T[],
    low: number = 0,
    high: number = array.length - 1,
    value: T,
    compareFn = defaultCompare,
): number {
    // 结果值的索引
    let result: number = DOES_NOT_EXIST;
    // 递归的边界条件
    if (low <= high) {
        // 待搜索区的中间值
        const mid: number = low + Math.floor((high - low) / 2);
        const midValue: T = array[mid];

        // 待搜索值比中间值小，证明待搜索值在左区间，需要将最大值索引替换成mid-1
        if (compareFn(value, midValue) === Compare.LESS_THAN) {
            result = binarySearchVisit(array, low, mid - 1, value, compareFn);
        }
        // 待搜索值比中间值大，证明待搜索值在右区间，需要将最小值索引替换成mid+1
        else if (compareFn(value, midValue) === Compare.BIGGER_THAN) {
            result = binarySearchVisit(array, mid + 1, high, value, compareFn);
        }
        // 待搜索值和中间值相等，找到了，直接返回
        else {
            result = mid;
        }
    }
    return result;
}
